package Sortion;
public class QuickSortHare{
    public static void main(String[] args) {
        int[] arr = {34, 67, 334, 1, 45, 76, 87, 8};
        QuickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    // 假设按照升序对 array 数组中的 [left, right] 区间进行排序
    public static void QuickSort(int[] array, int left, int right) {
        if (left >= right) {
            return; // 改正了递归的终止条件
        }

        // 按照基准值对 array 数组的 [left, right] 区间中的元素进行划分
        int div = partionHare(array, left, right);

        // 划分成功后以 div 为边界形成了左右两部分 [left, div) 和 [div+1, right)
        // 递归排 [left, div)
        QuickSort(array, left, div - 1);

        // 递归排 [div+1, right]
        QuickSort(array, div + 1, right);
    }

    // 实现基于 Hoare 分区的快速排序
    public static int partionHare(int[] arr, int left, int right) {
        int div = arr[left]; // 基准值
        while (left < right) {
            while (left < right && arr[right] >= div) {
                right--;
            }
            while (left < right && arr[left] <= div) {
                left++;
            }
            swap(arr, left, right); // 交换
        }
        swap(arr, left, div); // 基准值归位
        return left; // 返回基准值的新位置
    }

    // 交换方法
    public static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}
